package com.hyc.algorithm.tree;


import com.hyc.algorithm.Node.TreeNode;

import java.util.Arrays;

/**
 * @projectName: DataStructure
 * @package: com.hyc.algorithm.tree
 * @className: BeforeAndInReductionTree
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/4/4 16:25
 * @version: 1.0
 */
public class BeforeAndInReductionTree {
    public static void main(String[] args) {
        int[] pre = new int[]{1, 2, 4, 5, 3, 6};
        int[] mid = new int[]{4, 2, 5, 1, 3, 6};
        TreeNode result = buildTree(pre, mid);
        System.out.println(result);
    }

    public static TreeNode buildTree(int[] qian, int[] zhong) {
        if (qian == null || zhong == null || qian.length == 0 || zhong.length == 0 || qian.length != zhong.length) {
            return null;
        }
        //   从前序遍历中找到根节点
        TreeNode root = new TreeNode(qian[0]);
        int rootindex = 0;
        int rootval = root.val;
        //从中序数组中找到 root
        for (int i = 0; i < zhong.length; i++) {
            if (zhong[i] == rootval) {
                rootindex = i;
            }
        }
        //找到左子树的前序和中序
        int[] leftZhong = Arrays.copyOfRange(zhong, 0, rootindex);
        int[] leftQian = Arrays.copyOfRange(qian, 1, rootindex + 1);
        //找到右子树的前序和中序
        int[] rightZhong = Arrays.copyOfRange(zhong, rootindex + 1, zhong.length);
        int[] rightQian = Arrays.copyOfRange(qian, rootindex + 1, qian.length);
        //    递归构建左右子树
        TreeNode left = buildTree(leftQian, leftZhong);
        TreeNode right = buildTree(rightQian, rightZhong);
        //    给根节点添加左右子树
        root.left = left;
        root.right = right;
        return root;
    }
}
